public class ReverseBetween {
    /**
     * 链表内指定区间反转
     * 
     * 反转链表时，返回的是反转后的头节点，需要再次遍历才能得到新链表的尾节点。
     * 输入：{1,2,3,4,5},2,4
        返回值：{1,4,3,2,5}
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null || head.next == null || m >= n) {
            return head;
        }
        ListNode p = head, begin_pre = null, end = null;
        for (int i = 0; i < n; ++i) {
            if (i == m-2) {
                begin_pre = p;
            }
            if (i == n-1) {
                end = p;
            }
            p = p.next;
        }
        ListNode end_next = end.next;
        end.next = null;
        if (begin_pre == null) {
            ListNode reverseHead = reverse(head);
            ListNode tail = getTail(reverseHead);
            tail.next = end_next;
            return reverseHead;
        }
        ListNode reverseHead = reverse(begin_pre.next);
        begin_pre.next = reverseHead;
        ListNode tail = getTail(reverseHead);
        tail.next = end_next;
        return head;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private ListNode getTail(ListNode head) {
        ListNode p = head;
        while (p != null && p.next != null) {
            p = p.next;
        }
        return p;
    }
}
